package mine.code.question.动态规划;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 * 输入: n = 2
 * 输出: [0,1,1]
 * 解释:
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 *
 * @author caijinnan
 */
public class 前n数字二进制中1的个数 {

    @Test
    public void run() {
        System.out.println(Arrays.toString(countBits(5)));
    }


    public int[] countBits(int n) {
        //dp[i] = i%2!=0 dp[i-1] +1 | dp[i/2]
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2];
            } else {
                dp[i] = dp[i - 1] + 1;
            }
        }
        return dp;
    }
}
